package com.cuz.series.binarytree;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
    }

    static class Node {
        Node pre;
        Node next;
        int key ;
        int val;
    }

    int maxSize;
    int size=0;
    Node head;
    Node tail;

    Map<Integer,Node> map = new HashMap<>();
    public LRUCache(int capacity) {
        maxSize = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if(n == null){
            return -1;
        }

        adjustToHead(n);

        return n.val;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if(n == null){
            n = new Node();
            n.val = value;
            n.key = key;
            map.put(key,n);
            size++;
        }else{
            n.val = value;
        }
        adjustToHead(n);
    }

    //将节点移动到头部 如果容量超过需要删除尾部节点
    void adjustToHead(Node n){
        if(n == head.next){
            removeTailIfNeed();
            return;
        }

        Node sourceFirst = head.next;
        if(n.pre != null){
            n.pre.next = n.next;
            n.next.pre = n.pre;
        }
        n.next = sourceFirst;
        sourceFirst.pre = n;
        n.pre = head;
        head.next = n;
        removeTailIfNeed();
    }

    void removeTailIfNeed(){
        if(size>maxSize){
            map.remove(tail.pre.key);
            size -- ;
            Node needRemove = tail.pre;
            needRemove.pre.next = tail;
            tail.pre = needRemove.pre;
        }

    }
}
